/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-01
 * Time: 14:26
 */

public class Solution {
    public int[] countBits(int n) {
        int count = 0;
        int[] arr = new int[n+1];
        arr[0] = 0;
        for (int i = 1;i <= n;i++) {
            arr[i] = getNum(i);
        }
        return arr;
    }

    /**
     *  计算一个数字中 1 的个数
     * @param n
     * @return
     */
    public int getNum(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n &= (n-1);
        }
        return count;
    }


    /**
      因为是要挨个求某个数字中 1 的个数
      所以可以用动态规划
      一个数中 1 的个数比 "将这个数的最高位的 1 去掉后的那个数字" 中 1 的个数多 1
      如 68 中 1 的个数比 (68-64)=4 中 1 的个数多 1
      而 4 中 1 的个数已经被求出来了
      dp[i] = dp[(i - 最高位中的 1 )] + 1
      所以要以及记录当前的最高位是谁, 并且一直变化
      如果 n & (n - 1) == 0 , 那么就说明这个数字就是 2 的正数次幂, 就是当前的最高位
     * @param n
     * @return
     */
    public int[] countBits2(int n) {
        int[] arr = new int[n+1];
        arr[0] = 0;
        // 记录最高有效位的值
        int highBit = 0;
        for (int i = 1;i <= n;i++) {
            if ((i & (i-1)) == 0) {
                highBit = i;
            }
            // 当前这个数中 1 的个数比去掉最高位后那个数 中 1 的个数多 1
            arr[i] = arr[i-highBit] + 1;
        }
        return arr;
    }
}
